package leetcode.ge100;

import java.util.HashSet;

class Solution_160 {

	class ListNode {
		int val;
		ListNode next;

		ListNode(int x) {
			val = x;
		}
	}

	public static void main(String[] args) {
	}

	private HashSet<ListNode> set = new HashSet<ListNode>();

	public ListNode getIntersectionNode(ListNode headA, ListNode headB) {

		if (headA == null || headB == null)
			return null;

		boolean endA = false, endB = false;

		while (!endA || !endB) {
			if (!endA) {
				if (!set.add(headA)) {
					return headA;
				}
				if (headA.next != null) {
					headA = headA.next;
				} else {
					endA = true;
				}
			}
			if (!endB) {
				if (!set.add(headB)) {
					return headB;
				}
				if (headB.next != null) {
					headB = headB.next;
				} else {
					endB = true;
				}
			}
		}
		return null;
	}

}
